package factor;

import java.util.ArrayList;
import java.util.Random;

import util.Util;

public class PollardP {

	public static int pollardP(int n)
	{
		Random rnd = Util.getRnd();
		int b = rnd.nextInt(n);
		ArrayList<Integer> list = Util.getSmooth(b);
		int m = 1;
		
		for(int i : list)
			m *= i;
		
		int a = rnd.nextInt(n - 4) + 2;
		if(n % a == 0) return a;
		
		int g = Util.nzd((int) Math.pow(a, m) - 1, n);
		
		if(g > 1 && g < n)
			return g;
		else
			return pollardP(n);
	}

	public static void main(String[] args) {
		System.out.println(pollardP(25));
	}

}
